/**
 * 给定一个包含非负整数的 mxn网格grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 *
 * 说明：每次只能向下或者向右移动一步。
 *
 *
 *
 * 链接：https://leetcode.cn/problems/minimum-path-sum
 */
class MinPathSum {
    /**
     * 状态：
     *
     *  F(i, j): 前i个物品放入大小为j的背包中所获得的最大价值
     * 状态递推：对于第i个商品，有一种例外，装不下，两种选择，放或者不放
     *
     *  如果装不下：此时的价值与前i-1个的价值是一样的
     *
     *  F(i,j) = F(i-1,j)
     *
     *  如果可以装入：需要在两种选择中找最大的
     *
     *  F(i, j) = max{F(i-1,j), F(i-1, j - A[i]) + V[i]}
     *
     *  F(i-1,j): 表示不把第i个物品放入背包中， 所以它的价值就是前i-1个物品放入大小为j的背包的最大价值
     *
     *  F(i-1, j - A[i]) + V[i]：表示把第i个物品放入背包中，价值增加V[i],但是需要腾出j - A[i]的大小放第i
     *
     * 个商品
     * 初始化：第0行和第0列都为0，表示没有装物品时的价值都为0
     *
     *  F(0,j) = F(i,0) = 0
     *
     * 返回值：F(n,m)
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
       int row=grid.length;
       int col=grid[0].length;
       for(int i=1;i<col;i++) {
           grid[0][i]=grid[0][i-1]+grid[0][i];
       }
       for(int i=1;i<row;i++) {
           grid[i][0]=grid[i-1][0]+grid[i][0];
       } 
       for(int i=1;i<row;i++) {
           for(int j=1;j<col;j++) {
               grid[i][j]=Math.min(grid[i][j-1],grid[i-1][j])+grid[i][j];
           }
       }
       return grid[row-1][col-1];
    }
}